[01] >> ACID_QUEEN (Luna "Transaction" Patel)

╭─────────────────╮
│ ACID_QUEEN.LOG  │
╰─────────────────╯

CARACTERÍSTICAS:

• Idade: 34

• Background: PhD em Sistemas Distribuídos (abandonado após O Incidente™)

• Workspace: 6 monitores, 2 para logs de transação, 1 só para monitorar heartbeats

• Vestuário: Jaqueta de couro preta com patches de comandos SQL, colar com pendrive de backup

• Trauma: Perdeu 1M em transações devido a um bug de concorrência em 2019

• Vícios: Café preto, monitoramento compulsivo de logs, paranoia com consistência

• Hobbies: Coleciona logs de erros famosos, pratica meditação extrema durante deployments

CITAÇÕES TÍPICAS:

"Consistência eventual é como relacionamento aberto: alguém sempre sai machucado." "Durabilidade não é garantia, é uma prece aos deuses dos dados." "Prefiro perder um braço a perder consistência transacional."

[02] >> NOSQL_PUNK (Jack "Document" Thompson)

╭──────────────────╮
│ NOSQL_PUNK.JSON  │
╰──────────────────╯

CARACTERÍSTICAS:

• Idade: 29

• Background: Dropout de Ciência da Computação, guru de startups

• Workspace: Laptop coberto de stickers anti-SQL, rodando exclusivamente em modo escuro

• Vestuário: Moletom rasgado com "DROP TABLE rules;" estampado, múltiplos piercings USB

• Trauma: Foi forçado a usar stored procedures em seu primeiro emprego

• Vícios: Energy drinks, JavaScript, schemas dinâmicos

• Hobbies: Criar manifestos contra normalização, converter DBs relacionais para NoSQL

CITAÇÕES TÍPICAS:

"Schema é só uma construção social." "Se seu documento tem menos de 16MB, você não está vivendo o suficiente." "ACID? Prefiro BASE - Basically Available, Soft state, Eventually consistent."

[03] >> SECURITY_PHANTOM (Ghost "Zero Trust" Zhang)

╭────────────────────────╮
│ SECURITY_PHANTOM.CRYPT │
╰────────────────────────╯

CARACTERÍSTICAS:

• Idade: [REDACTED]

• Background: Ex-black hat, 10 anos em agência governamental não especificada

• Workspace: Ar-gapped laptop, 3 VPNs simultâneas, teclado com fingerprint

• Vestuário: Sobretudo com Faraday cage embutida, óculos anti-reconhecimento facial

• Trauma: Descobriu backdoors em todos os sistemas que já auditou

• Vícios: Criptografia, autenticação multi-fator, paranoia

• Hobbies: Criar CTFs impossíveis, auditar código open source por diversão

CITAÇÕES TÍPICAS:

"Sua senha forte é minha senha fraca." "Confie em todos os usuários... em verificar duas vezes." "Se você pode acessar, eles também podem."

[04] >> BACKUP_PRIESTESS (Maria "Recovery Point" Santos)

╭──────────────────────╮
│ BACKUP_PRIESTESS.BAK │
╰──────────────────────╯

CARACTERÍSTICAS:

• Idade: 41

• Background: Veterana de múltiplos desastres de recuperação

• Workspace: Sala repleta de HDs externos, rituais de backup escritos nas paredes

• Vestuário: Colete tático cheio de SSDs, colar de USBs bootáveis

• Trauma: Perdeu TCC por não ter backup (2003, nunca esquecerá)

• Vícios: Comprar storage, criar scripts de backup, testar disaster recovery

• Hobbies: Colecionar mídias antigas, realizar rituais de backup à meia-noite

CITAÇÕES TÍPICAS:

"Um backup é nenhum backup. Três backups é um começo." "Seu sistema não está realmente em produção até ter falhado e recuperado." "Snapshot é para os fracos. Eu quero full backup com prova de vida."

[05] >> TIME_LORD (Dr. Eve "Timestamp" Williams)

╭───────────────────╮
│ TIME_LORD.CHRONO  │
╰───────────────────╯

CARACTERÍSTICAS:

• Idade: Depende do timezone

• Background: Doutorado em Física Quântica reconvertida para DBA

• Workspace: Múltiplos relógios mostrando diferentes timezones, calendário juliano na parede

• Vestuário: Roupa com padrão de timestamps, relógio em cada pulso (UTC e local)

• Trauma: Sistema caiu durante mudança de horário de verão

• Vícios: Sincronização de tempo, debates sobre ISO 8601

• Hobbies: Debugar race conditions, colecionar relógios atômicos

CITAÇÕES TÍPICAS:

"Tempo é relativo, mas timestamp é absoluto." "Em qual timeline você quer fazer backup?" "Não me fale de datas sem me dizer o timezone."

[REGRA 01] >> Backup é Vida

╭──────────────────────────╮
│ BACKUP_PRIESTESS.ALERTA  │
├──────────────────────────┤
│ "Faça backup antes que   │
│  o backup faça você."    │
╰──────────────────────────╯

• Mantenha backups atualizados de TODO o seu trabalho

• Configure auto-save em seus editores

• Use controle de versão para TUDO

• Nunca confie em um único ponto de armazenamento

[REGRA 02] >> Segurança Primeiro

╭──────────────────────────╮
│ SECURITY_PHANTOM.AVISO   │
├──────────────────────────┤
│ "Paranoia é apenas bom   │
│  senso no nível 11."     │
╰──────────────────────────╯

• Use senhas fortes e gerenciador de senhas

• Ative autenticação de dois fatores

• Mantenha seu sistema atualizado

• Criptografe dados sensíveis

[REGRA 03] >> Consistência é Chave

╭──────────────────────────╮
│ ACID_QUEEN.MANDAMENTO    │
├──────────────────────────┤
│ "Seja ACID ou não seja." │
╰──────────────────────────╯

• Mantenha seus ambientes sincronizados

• Use versionamento semântico

• Documente todas as alterações

• Teste antes de qualquer commit

[REGRA 04] >> Flexibilidade Controlada

╭──────────────────────────╮
│ NOSQL_PUNK.MANIFESTO     │
├──────────────────────────┤
│ "Schema é sugestão,      │
│  caos é liberdade."      │
╰──────────────────────────╯

• Adapte-se às mudanças, mas mantenha o controle

• Use as ferramentas certas para cada problema

• Não se prenda a um único paradigma

• Mantenha a mente aberta para novas soluções

[REGRA 05] >> Tempo é Crítico

╭──────────────────────────╮
│ TIME_LORD.DECRETO        │
├──────────────────────────┤
│ "UTC ou nada feito."     │
╰──────────────────────────╯

• Sempre use UTC para timestamps

• Documente fusos horários explicitamente

• Considere aspectos temporais no design

• Planeje para mudanças de horário de verão

Ferramentas Essenciais

╔════════════════════════════════╗
║ TOOLS.REQUIRED                 ║
╠════════════════════════════════╣
║ ► Editor de código confiável   ║
║ ► Cliente SQL robusto          ║
║ ► Ferramentas de modelagem     ║
║ ► Software de virtualização    ║
║ ► Gerenciador de versão        ║
╚════════════════════════════════╝

Práticas de Sobrevivência

╔════════════════════════════════╗
║ SURVIVAL.PRACTICES             ║
╠════════════════════════════════╣
║ ► Commits frequentes           ║
║ ► Testes automatizados         ║
║ ► Documentação atualizada      ║
║ ► Monitoramento constante      ║
║ ► Backup redundante            ║
╚════════════════════════════════╝

Em Caso de Falha

1. NÃO ENTRE EM PÂNICO

2. Consulte os logs

3. Isole o problema

4. Documente o ocorrido

5. Implemente correção

6. Atualize documentação

Em Caso de Perda de Dados

1. MANTENHA A CALMA

2. Pare todas as operações

3. Acesse backups

4. Inicie recuperação

5. Valide integridade

6. Documente processo

1. Motor de Armazenamento

• Gerenciamento de armazenamento físico

• Implementação de estruturas de dados

• Organização de páginas e registros

• Estratégias de compressão e codificação

2. Gerenciador de Buffer

• Gerenciamento de memória cache

• Políticas de substituição de páginas

• Otimização de E/S

• Estratégias de pré-carregamento e gravação posterior

3. Processador de Consultas

• Analisador e validador de consultas

• Otimizador de consultas

• Executor de planos

• Cache de resultados

4. Gerenciador de Transações

• Controle de concorrência

• Isolamento de transações

• Gerenciamento de bloqueios

• Detecção de impasses

5. Sistema de Recuperação

• Registro antecipado de alterações

• Gerenciamento de pontos de verificação

• Recuperação após falhas

• Backup e restauração

Camada de Armazenamento

1. Gerenciamento de Disco

   • Alocação de espaço

   • Gerenciamento de blocos

   • Escalonamento de E/S

   • Configurações RAID

2. Estruturas de Indexação

   • Árvores B e variantes

   • Índices hash

   • Índices bitmap

   • Índices especializados

3. Gerenciamento de Buffer

   • Políticas LRU/MRU

   • Rastreamento de páginas sujas

   • Substituição de páginas

   • Mapeamento de memória

Camada de Processamento

1. Motor de Consultas

   • Análise sintática

   • Análise semântica

   • Reescrita de consultas

   • Otimização baseada em custos

2. Motor de Execução

   • Processamento em pipeline

   • Execução paralela

   • Gerenciamento de recursos

   • Otimização em tempo de execução

1. Arquitetura Monolítica

• Características

  • Implantação em nó único

  • Arquitetura compartilhada

  • Forte consistência

  • Simplicidade operacional

• Considerações

  • Limites de escalabilidade vertical

  • Ponto único de falha

  • Manutenção simplificada

  • Menor complexidade operacional

2. Arquitetura Distribuída

• Características

  • Implantação multi-nó

  • Arquitetura sem compartilhamento

  • Escalabilidade horizontal

  • Alta disponibilidade

• Componentes Específicos

  • Processador de consultas distribuído

  • Protocolos de consenso

  • Gerenciador de replicação

  • Gerenciador de particionamento

3. Arquitetura Híbrida

• Características

  • Combinação de abordagens

  • Flexibilidade de implantação

  • Compromissos personalizáveis

  • Adaptabilidade contextual

Métricas Fundamentais

1. Taxa de Transferência

   • Transações por segundo (TPS)

   • Consultas por segundo (QPS)

   • Taxa de transferência de dados

2. Latência

   • Tempo de resposta

   • Tempo de processamento

   • Tempo de espera E/S

3. Utilização de Recursos

   • Uso de CPU

   • Consumo de memória

   • Largura de banda de E/S

   • Utilização de rede

Otimização

1. Otimização de Consultas

   • Otimização de plano de execução

   • Utilização de índices

   • Estratégias de junção

   • Visões materializadas

2. Gerenciamento de Recursos

   • Pool de conexões

   • Gerenciamento de threads

   • Alocação de memória

   • Escalonamento de E/S

1. Escalabilidade

• Escalabilidade horizontal vs. vertical

• Particionamento de dados

• Replicação

• Balanceamento de carga

2. Disponibilidade

• Redundância

• Mecanismos de failover

• Recuperação de desastres

• Estratégias de backup

3. Consistência

• Modelos de consistência

• Compromissos CAP

• Níveis de isolamento

• Gerenciamento de atraso de replicação

4. Segurança

• Autenticação

• Autorização

• Criptografia

• Registro de auditoria

1. Estrutura de Páginas

• Tamanho fixo (tipicamente 4KB-16KB)

• Cabeçalho da página

• Área de dados

• Diretório de slots

• Gestão de espaço livre

2. Formatos de Registro

• Registros de tamanho fixo

• Registros de tamanho variável

• Técnicas de compressão

• Gestão de campos nulos

3. Organização de Arquivos

• Heap files

• Arquivos sequenciais

• Arquivos hash

• Arquivos clusterizados

1. Compressão de Dados

• Compressão de página

• Compressão de registro

• Dicionário de dados

• Técnicas específicas por tipo

2. Particionamento

• Horizontal

• Vertical

• Por faixa

• Por hash

• Composto

3. Estratégias de Alocação

• Alocação contígua

• Alocação encadeada

• Alocação indexada

• Extensible hashing

1. Organização Física

• Clustering

• Sequenciamento

• Interleaving

• Striping

2. Prefetching

• Prefetch sequencial

• Prefetch baseado em padrões

• Prefetch adaptativo

• Gestão de buffer inteligente

3. Write Optimization

• Write-ahead logging

• Group commit

• Background writing

• Write buffering

1. Métricas de Avaliação

• Taxa de acertos no buffer

• Tempo médio de acesso

• Throughput de I/O

• Utilização do espaço

2. Trade-offs

• Espaço vs. Velocidade

• Complexidade vs. Flexibilidade

• Consistência vs. Performance

• Redundância vs. Eficiência

1. Novas Tecnologias

• NVMe e Storage Class Memory

• Armazenamento columnnar

• Estruturas híbridas

• In-memory databases

2. Otimizações Modernas

• Compressão adaptativa

• Indexação automática

• Auto-tuning

• Machine learning aplicado

1. Componentes Físicos

• Pratos (Platters)

• Cabeças de leitura/escrita

• Setores e trilhas

• Cilindros

2. Características Operacionais

• Tempo de seek

• Latência rotacional

• Taxa de transferência

• Tempo de acesso médio

1. Blocos de Disco

• Tamanho do bloco

• Alinhamento

• Fragmentação

• Overhead

2. Estratégias de Alocação

• Contígua

• Linked

• Indexed

• Extents

1. Técnicas de Posicionamento

• Zoneamento

• Agrupamento

• Desfragmentação

• Balanceamento

2. Padrões de Acesso

• Sequencial

• Random

• Mixed

• Batch

1. Métricas Importantes

• IOPS (I/O por segundo)

• Throughput

• Latência

• Queue depth

2. Gargalos Comuns

• Seek time

• Rotational delay

• Transfer bottlenecks

• Queue congestion

1. RAID

• RAID 0 (Striping)

• RAID 1 (Mirroring)

• RAID 5 (Striping with parity)

• RAID 10 (Striping and mirroring)

2. Técnicas Modernas

• SSD optimization

• NVMe considerations

• Hybrid storage

• Tiered storage

1. Ferramentas de Diagnóstico

• I/O stats

• Disk usage

• Performance counters

• Queue metrics

2. Manutenção Preventiva

• Desfragmentação regular

• Space monitoring

• Performance tracking

• Health checks

1. Estruturas Principais

• Frame Table

• Page Table

• Hash Table

• Free List

• Dirty List

2. Componentes de Controle

• Descritores de página

• Contadores de pin

• Bits de estado

• Timestamps

1. Algoritmos Básicos

• LRU (Least Recently Used)

• Clock

• MRU (Most Recently Used)

• Random

2. Algoritmos Avançados

• LRU-K

• 2Q

• ARC (Adaptive Replacement Cache)

• CLOCK-Pro

1. Técnicas de Prefetching

• Sequential

• Index-based

• Pattern-based

• Adaptive

2. Write Strategies

• Force/No-Force

• Steal/No-Steal

• Group Commit

• Background Writing

1. Mecanismos de Latch

• Shared latches

• Exclusive latches

• Latch queuing

• Deadlock prevention

2. Buffer Fix

• Pin count

• Fix duration

• Unfix operations

• Reference counting

1. Métricas Principais

• Hit ratio

• Buffer utilization

• Write frequency

• Eviction rate

2. Ferramentas de Análise

• Buffer pool statistics

• Page access patterns

• I/O monitoring

• Memory pressure

1. Parâmetros Críticos

• Buffer pool size

• Page size

• Number of partitions

• Write threshold

2. Otimizações Específicas

• Multiple buffer pools

• Page compression

• Memory-mapped I/O

• Direct I/O

1. Recovery Integration

• Checkpoint processing

• Redo logging

• Undo logging

• Recovery actions

2. Consistency Management

• Page consistency

• Buffer coherency

• Cache invalidation

• Version control

1. Novas Tecnologias

• Non-volatile memory

• Hardware transactional memory

• RDMA-aware buffering

• Smart storage

2. Otimizações Emergentes

• ML-based prediction

• Adaptive algorithms

• Hybrid storage integration

• Cloud-optimized buffering

1. Conceitos Básicos

• Chaves de busca

• Registros de índice

• Densidade de índice

• Seletividade

2. Classificação

• Primário vs. Secundário

• Denso vs. Esparso

• Clustered vs. Non-clustered

• Single-level vs. Multi-level

1. Árvores B

• Propriedades

• Operações básicas

• Balanceamento

• Split e Merge

2. Árvores B+

• Estrutura de folhas

• Sequência de folhas

• Range queries

• Bulk loading

1. Hashing Estático

• Funções hash

• Tratamento de colisões

• Fator de carga

• Overflow chains

2. Hashing Dinâmico

• Directory structure

• Split operations

• Merge operations

• Directory management

1. Estrutura Básica

• Vetores de bits

• Operações lógicas

• Compressão

• Atualização

2. Otimizações

• Encoding schemes

• Compression techniques

• Cardinality handling

• Update strategies

1. Índices Especializados

• Spatial indexes

• Temporal indexes

• Full-text indexes

• JSON indexes

2. Estruturas Híbridas

• Hash-tree combination

• Bitmap-tree indexes

• Multi-dimensional indexes

• Adaptive indexes

1. Estratégias de Criação

• Index selection

• Key selection

• Storage allocation

• Build optimization

2. Manutenção

• Statistics update

• Reorganization

• Rebuild operations

• Monitoring

1. Métricas de Avaliação

• Access time

• Storage overhead

• Maintenance cost

• Query impact

2. Considerações Práticas

• Workload analysis

• Storage constraints

• Update frequency

• Query patterns

1. Novas Tecnologias

• Machine learning indexes

• Learned index structures

• Hardware-aware indexes

• Cloud-optimized indexes

2. Otimizações Emergentes

• Auto-indexing

• Adaptive indexing

• Predictive maintenance

• Quantum-resistant structures

Definição do Nó

class BNode {
    int[] keys;          // array de chaves
    BNode[] children;    // array de ponteiros
    int keyCount;        // número de chaves
    boolean isLeaf;      // flag de folha
    int minDegree;       // grau mínimo da árvore
}

class BTree {
    BNode root;          // raiz da árvore
    int minDegree;       // grau mínimo da árvore
    
    public BTree(int degree) {
        this.root = null;
        this.minDegree = degree;
    }
}

Propriedades Fundamentais

• Ordem da árvore (t)

• Número mínimo de chaves (t-1)

• Número máximo de chaves (2t-1)

• Número mínimo de filhos (t)

• Número máximo de filhos (2t)

1. Busca

BNode search(BNode node, int key) {
    int i = 0;
    while (i < node.keyCount && key > node.keys[i]) {
        i++;
    }
    
    if (i < node.keyCount && key == node.keys[i]) {
        return node;
    }
    
    if (node.isLeaf) {
        return null;
    }
    
    return search(node.children[i], key);
}

2. Inserção

void splitChild(BNode parent, int index, BNode child) {
    BNode newNode = new BNode(child.minDegree);
    newNode.isLeaf = child.isLeaf;
    newNode.keyCount = minDegree - 1;
    
    // Copiar chaves superiores para novo nó
    for (int j = 0; j < minDegree - 1; j++) {
        newNode.keys[j] = child.keys[j + minDegree];
    }
    
    // Se não for folha, copiar ponteiros correspondentes
    if (!child.isLeaf) {
        for (int j = 0; j < minDegree; j++) {
            newNode.children[j] = child.children[j + minDegree];
        }
    }
    
    child.keyCount = minDegree - 1;
    
    // Mover ponteiros do pai
    for (int j = parent.keyCount; j >= index + 1; j--) {
        parent.children[j + 1] = parent.children[j];
    }
    
    parent.children[index + 1] = newNode;
    
    // Mover chaves do pai e inserir chave mediana
    for (int j = parent.keyCount - 1; j >= index; j--) {
        parent.keys[j + 1] = parent.keys[j];
    }
    parent.keys[index] = child.keys[minDegree - 1];
    parent.keyCount++;
}

void insert(int key) {
    if (root == null) {
        root = new BNode(minDegree);
        root.keys[0] = key;
        root.keyCount = 1;
        root.isLeaf = true;
    } else {
        if (root.keyCount == 2 * minDegree - 1) {
            BNode newRoot = new BNode(minDegree);
            newRoot.children[0] = root;
            splitChild(newRoot, 0, root);
            insertNonFull(newRoot, key);
            root = newRoot;
        } else {
            insertNonFull(root, key);
        }
    }
}

3. Remoção

void remove(BNode node, int key) {
    int idx = findKey(node, key);
    
    if (idx < node.keyCount && node.keys[idx] == key) {
        if (node.isLeaf) {
            removeFromLeaf(node, idx);
        } else {
            removeFromNonLeaf(node, idx);
        }
    } else {
        if (node.isLeaf) {
            return;  // Chave não encontrada
        }
        
        boolean flag = (idx == node.keyCount);
        
        if (node.children[idx].keyCount < minDegree) {
            fill(node, idx);
        }
        
        if (flag && idx > node.keyCount) {
            remove(node.children[idx - 1], key);
        } else {
            remove(node.children[idx], key);
        }
    }
}

1. Cache-Conscious

class CacheOptimizedNode {
    private static final int CACHE_LINE_SIZE = 64;
    private long[] keys;  // Alinhado em 64 bytes
    private long[] children;
    
    public CacheOptimizedNode(int degree) {
        keys = new long[2 * degree - 1];
        children = new long[2 * degree];
    }
}

2. Concorrência

class ConcurrentBNode {
    private ReentrantReadWriteLock lock;
    private volatile boolean isDeleted;
    
    public void acquireReadLock() {
        lock.readLock().lock();
    }
    
    public void acquireWriteLock() {
        lock.writeLock().lock();
    }
}

1. Copy-on-Write

class COWBNode {
    private final int[] keys;
    private final BNode[] children;
    private final AtomicReference<COWBNode> next;
    
    public COWBNode copy() {
        COWBNode newNode = new COWBNode(keys.clone(), 
                                      children.clone());
        return newNode;
    }
}

2. Bulk Loading

void bulkLoad(int[] sortedKeys) {
    int leafSize = 2 * minDegree - 1;
    List<BNode> leaves = new ArrayList<>();
    
    // Criar nós folha
    for (int i = 0; i < sortedKeys.length; i += leafSize) {
        BNode leaf = new BNode(minDegree);
        leaf.isLeaf = true;
        int count = Math.min(leafSize, 
                           sortedKeys.length - i);
        System.arraycopy(sortedKeys, i, 
                        leaf.keys, 0, count);
        leaf.keyCount = count;
        leaves.add(leaf);
    }
    
    // Construir níveis superiores
    buildUpperLevels(leaves);
}

1. Buffer Management

class BufferPool {
    private final int capacity;
    private final Map<Long, BNode> pages;
    private final LRUCache<Long> lru;
    
    public BNode getPage(long pageId) {
        BNode page = pages.get(pageId);
        if (page != null) {
            lru.access(pageId);
            return page;
        }
        return loadFromDisk(pageId);
    }
}

2. Recovery

class LogRecord {
    enum Type { INSERT, DELETE, SPLIT, MERGE }
    private final Type type;
    private final long pageId;
    private final int key;
    private final byte[] beforeImage;
    private final byte[] afterImage;
}

1. Monitoramento

2. Manutenção

void rebalance(BNode node) {
    if (node.keyCount < minDegree - 1) {
        mergeOrRedistribute(node);
    } else if (node.keyCount > 2 * minDegree - 1) {
        split(node);
    }
    
    if (!node.isLeaf) {
        for (int i = 0; i <= node.keyCount; i++) {
            rebalance(node.children[i]);
        }
    }
}

1. Iterator

class BTreeIterator implements Iterator<Integer> {
    private final Stack<BNode> path;
    private final Stack<Integer> indices;
    
    public boolean hasNext() {
        return !path.isEmpty();
    }
    
    public Integer next() {
        BNode current = path.peek();
        int idx = indices.peek();
        
        int key = current.keys[idx];
        advanceToNext();
        return key;
    }
}

2. Range Scan

List<Integer> rangeSearch(int start, int end) {
    List<Integer> result = new ArrayList<>();
    rangeSearchRecursive(root, start, end, result);
    return result;
}

void rangeSearchRecursive(BNode node, int start, 
                         int end, List<Integer> result) {
    int i = 0;
    
    while (i < node.keyCount && node.keys[i] < start) {
        i++;
    }
    
    while (i < node.keyCount && node.keys[i] <= end) {
        if (!node.isLeaf) {
            rangeSearchRecursive(node.children[i], 
                               start, end, result);
        }
        result.add(node.keys[i]);
        i++;
    }
    
    if (!node.isLeaf && i <= node.keyCount) {
        rangeSearchRecursive(node.children[i], 
                           start, end, result);
    }
}

1. Funções Hash

class HashFunction {
    // Multiplicação
    long multiplyHash(String key, int tableSize) {
        long hash = 0;
        for (char c : key.toCharArray()) {
            hash = 31 * hash + c;
        }
        return Math.abs(hash % tableSize);
    }
    
    // FNV Hash
    long fnvHash(byte[] data) {
        long hash = 0xcbf29ce484222325L;
        for (byte b : data) {
            hash *= 0x100000001b3L;
            hash ^= b;
        }
        return hash;
    }
}

2. Tratamento de Colisões

class Node<K,V> {
    K key;
    V value;
    Node<K,V> next;
    
    Node(K key, V value) {
        this.key = key;
        this.value = value;
    }
}

class HashTable<K,V> {
    private Node<K,V>[] table;
    private int size;
    
    @SuppressWarnings("unchecked")
    public HashTable(int capacity) {
        table = (Node<K,V>[]) new Node[capacity];
        size = 0;
    }
    
    public void put(K key, V value) {
        int index = hash(key);
        Node<K,V> node = table[index];
        
        while (node != null) {
            if (node.key.equals(key)) {
                node.value = value;
                return;
            }
            node = node.next;
        }
        
        Node<K,V> newNode = new Node<>(key, value);
        newNode.next = table[index];
        table[index] = newNode;
        size++;
    }
}

class OpenAddressingHash<K,V> {
    private Entry<K,V>[] table;
    private int size;
    private static final double LOAD_FACTOR = 0.75;
    
    private static class Entry<K,V> {
        K key;
        V value;
        boolean isDeleted;
        
        Entry(K key, V value) {
            this.key = key;
            this.value = value;
        }
    }
    
    public V get(K key) {
        int index = findKey(key);
        return index != -1 ? table[index].value : null;
    }
    
    private int findKey(K key) {
        int hash = hash(key);
        int i = 0;
        
        while (i < table.length) {
            int j = (hash + probe(i)) % table.length;
            
            if (table[j] == null) return -1;
            if (!table[j].isDeleted && 
                table[j].key.equals(key)) {
                return j;
            }
            i++;
        }
        return -1;
    }
    
    private int probe(int i) {
        return i * i;  // Quadratic probing
    }
}

1. Linear Hashing

class LinearHash<K,V> {
    private ArrayList<Bucket<K,V>> buckets;
    private int splitPointer;
    private int level;
    private double loadFactor;
    
    private static class Bucket<K,V> {
        Map<K,V> entries;
        int localDepth;
        
        Bucket(int depth) {
            entries = new HashMap<>();
            localDepth = depth;
        }
    }
    
    public void insert(K key, V value) {
        int bucketIndex = getBucketIndex(key);
        Bucket<K,V> bucket = buckets.get(bucketIndex);
        
        bucket.entries.put(key, value);
        
        if (shouldSplit()) {
            split();
        }
    }
    
    private void split() {
        Bucket<K,V> oldBucket = buckets.get(splitPointer);
        Bucket<K,V> newBucket = new Bucket<>(level);
        
        // Redistribuir entradas
        Map<K,V> oldEntries = oldBucket.entries;
        oldBucket.entries = new HashMap<>();
        
        for (Map.Entry<K,V> entry : oldEntries.entrySet()) {
            int newIndex = getBucketIndex(entry.getKey());
            if (newIndex == splitPointer) {
                oldBucket.entries.put(entry.getKey(), 
                                    entry.getValue());
            } else {
                newBucket.entries.put(entry.getKey(), 
                                    entry.getValue());
            }
        }
        
        buckets.add(newBucket);
        splitPointer++;
        
        if (splitPointer == Math.pow(2, level)) {
            splitPointer = 0;
            level++;
        }
    }
}

2. Extendible Hashing

class ExtendibleHash<K,V> {
    private Directory<K,V> directory;
    private int globalDepth;
    
    private static class Directory<K,V> {
        Bucket<K,V>[] buckets;
        int size;
        
        @SuppressWarnings("unchecked")
        Directory(int size) {
            this.size = size;
            buckets = new Bucket[size];
        }
    }
    
    private static class Bucket<K,V> {
        Map<K,V> entries;
        int localDepth;
        static final int CAPACITY = 4;
        
        Bucket(int depth) {
            entries = new HashMap<>();
            localDepth = depth;
        }
        
        boolean isFull() {
            return entries.size() >= CAPACITY;
        }
    }
    
    public void insert(K key, V value) {
        int dirIndex = hash(key) & ((1 << globalDepth) - 1);
        Bucket<K,V> bucket = directory.buckets[dirIndex];
        
        if (bucket.isFull()) {
            if (bucket.localDepth == globalDepth) {
                doubleDirectory();
            }
            split(dirIndex);
            insert(key, value);
        } else {
            bucket.entries.put(key, value);
        }
    }
    
    private void split(int bucketIndex) {
        Bucket<K,V> oldBucket = directory.buckets[bucketIndex];
        Bucket<K,V> newBucket = new Bucket<>(oldBucket.localDepth + 1);
        
        Map<K,V> oldEntries = oldBucket.entries;
        oldBucket.entries = new HashMap<>();
        oldBucket.localDepth++;
        
        int mask = 1 << (oldBucket.localDepth - 1);
        for (Map.Entry<K,V> entry : oldEntries.entrySet()) {
            int newIndex = hash(entry.getKey()) & ((1 << oldBucket.localDepth) - 1);
            if ((newIndex & mask) == 0) {
                oldBucket.entries.put(entry.getKey(), entry.getValue());
            } else {
                newBucket.entries.put(entry.getKey(), entry.getValue());
            }
        }
        
        // Atualizar diretório
        for (int i = 0; i < directory.size; i++) {
            if (directory.buckets[i] == oldBucket && (i & mask) != 0) {
                directory.buckets[i] = newBucket;
            }
        }
    }
}

1. Cache-Conscious Hashing

class CacheOptimizedHash<K,V> {
    private static final int CACHE_LINE_SIZE = 64;
    private static final int ENTRIES_PER_BUCKET = 
        CACHE_LINE_SIZE / (8 + 8); // key + value ptr
    
    private static class Bucket<K,V> {
        long[] keys;
        V[] values;
        int size;
        
        @SuppressWarnings("unchecked")
        Bucket() {
            keys = new long[ENTRIES_PER_BUCKET];
            values = (V[]) new Object[ENTRIES_PER_BUCKET];
        }
    }
}

2. Concurrent Hashing

class ConcurrentHash<K,V> {
    private static final int SHARD_COUNT = 16;
    private final HashTable<K,V>[] shards;
    private final ReentrantLock[] locks;
    
    @SuppressWarnings("unchecked")
    public ConcurrentHash() {
        shards = new HashTable[SHARD_COUNT];
        locks = new ReentrantLock[SHARD_COUNT];
        
        for (int i = 0; i < SHARD_COUNT; i++) {
            shards[i] = new HashTable<>();
            locks[i] = new ReentrantLock();
        }
    }
    
    public V put(K key, V value) {
        int shardIndex = getShard(key);
        locks[shardIndex].lock();
        try {
            return shards[shardIndex].put(key, value);
        } finally {
            locks[shardIndex].unlock();
        }
    }
    
    private int getShard(K key) {
        return Math.abs(key.hashCode() % SHARD_COUNT);
    }
}

1. Bloom Filter

class BloomFilter<T> {
    private BitSet bitset;
    private int size;
    private int numHashFunctions;
    private HashFunction[] hashFunctions;
    
    public BloomFilter(int size, int numHash) {
        this.size = size;
        this.numHashFunctions = numHash;
        this.bitset = new BitSet(size);
        this.hashFunctions = new HashFunction[numHash];
        
        for (int i = 0; i < numHash; i++) {
            hashFunctions[i] = new HashFunction(i);
        }
    }
    
    public void add(T item) {
        for (HashFunction hf : hashFunctions) {
            bitset.set(hf.hash(item) % size);
        }
    }
    
    public boolean mightContain(T item) {
        for (HashFunction hf : hashFunctions) {
            if (!bitset.get(hf.hash(item) % size)) {
                return false;
            }
        }
        return true;
    }
}

2. Cuckoo Hashing

class CuckooHash<K,V> {
    private static final int MAX_LOOP = 100;
    private Entry<K,V>[][] tables;
    private HashFunction[] hashFunctions;
    
    private static class Entry<K,V> {
        K key;
        V value;
        
        Entry(K key, V value) {
            this.key = key;
            this.value = value;
        }
    }
    
    @SuppressWarnings("unchecked")
    public CuckooHash(int capacity) {
        tables = new Entry[2][capacity];
        hashFunctions = new HashFunction[]{
            new HashFunction(0),
            new HashFunction(1)
        };
    }
    
    public boolean insert(K key, V value) {
        Entry<K,V> entry = new Entry<>(key, value);
        
        for (int i = 0; i < MAX_LOOP; i++) {
            for (int j = 0; j < 2; j++) {
                int pos = hashFunctions[j].hash(key) % tables[j].length;
                Entry<K,V> temp = tables[j][pos];
                tables[j][pos] = entry;
                
                if (temp == null) return true;
                entry = temp;
            }
        }
        
        // Rehash needed
        return false;
    }
}

1. Métricas

class HashMetrics {
    private long collisions;
    private long resizes;
    private double loadFactor;
    private long[] bucketSizes;
    
    public void recordCollision() {
        collisions++;
    }
    
    public void recordResize() {
        resizes++;
    }
    
    public void updateLoadFactor(int entries, int capacity) {
        loadFactor = (double) entries / capacity;
    }
    
    public String getStats() {
        return String.format(
            "Collisions: %d\nResizes: %d\nLoad Factor: %.2f",
            collisions, resizes, loadFactor
        );
    }
}

2. Auto-tuning

class AdaptiveHash<K,V> {
    private static final double RESIZE_THRESHOLD = 0.75;
    private static final double COLLISION_THRESHOLD = 0.1;
    
    private HashTable<K,V> table;
    private HashMetrics metrics;
    
    public void tune() {
        if (metrics.getLoadFactor() > RESIZE_THRESHOLD) {
            resize(table.capacity() * 2);
        }
        
        if (metrics.getCollisionRate() > COLLISION_THRESHOLD) {
            changeHashFunction();
        }
    }
    
    private void changeHashFunction() {
        HashFunction[] candidates = {
            new MultiplyHash(),
            new FNVHash(),
            new MurmurHash()
        };
        
        // Avaliar e selecionar a melhor função
        HashFunction best = evaluateHashFunctions(candidates);
        table.setHashFunction(best);
    }
}

1. Escolha da Estrutura

2. Trade-offs

• Memória vs. Velocidade

• Complexidade vs. Flexibilidade

• Concorrência vs. Consistência

• Localidade vs. Distribuição

1. Estrutura Básica

• Mapeamento valor-bit

• Vetores binários

• Dicionário de valores

• Metadata

2. Tipos de Bitmap

• Simple bitmap

• Encoded bitmap

• Compressed bitmap

• Hierarchical bitmap

1. Operações Lógicas

• AND (Interseção)

• OR (União)

• NOT (Complemento)

• XOR (Diferença simétrica)

2. Manipulação

• Set bit

• Clear bit

• Flip bit

• Count bits

1. Técnicas de Compressão

• Run-length encoding

• Word-aligned hybrid

• Roaring bitmap

• EWAH compression

2. Estratégias de Encoding

• Range encoding

• Interval encoding

• Equality encoding

• Range-equality encoding

1. Cenários Ideais

• Baixa cardinalidade

• Consultas analíticas

• Operações em lote

• Data warehousing

2. Limitações

• Alta cardinalidade

• Frequentes atualizações

• Restrições de memória

• Overhead de manutenção

1. Métricas de Avaliação

• Densidade do bitmap

• Taxa de compressão

• Tempo de resposta

• Overhead de memória

2. Estratégias de Otimização

• Binning

• Particionamento

• Caching

• Paralelização

1. Considerações de Design

• Estrutura de armazenamento

• Estratégias de atualização

• Gerenciamento de memória

• Concorrência

2. Manutenção

• Reconstrução

• Compactação

• Estatísticas

• Monitoramento

1. Memória Primária

• Registradores

  • Velocidade: < 1ns

  • Capacidade: KB

  • Volatilidade: Sim

  • Custo: Muito Alto

• Cache

  • L1/L2/L3

  • Latência: 1-10ns

  • Capacidade: MB

  • Política de substituição

2. Memória Principal

• RAM

  • Acesso direto

  • Latência: ~100ns

  • Capacidade: GB

  • Gerenciamento dinâmico

• Memória Virtual

  • Paginação

  • Swapping

  • Page tables

  • TLB (Translation Lookaside Buffer)

3. Armazenamento Secundário

• SSD

  • Flash storage

  • Latência: µs

  • Wear leveling

  • TRIM support

• HDD

  • Discos magnéticos

  • Latência: ms

  • Fragmentação

  • Seek time

1. Políticas de Cache

• LRU (Least Recently Used)

• MRU (Most Recently Used)

• CLOCK

• ARC (Adaptive Replacement Cache)

2. Buffer Management

• Políticas de Substituição

  • Page replacement

  • Dirty page handling

  • Prefetching

  • Write-back/Write-through

• Otimizações

  • Sequential prefetch

  • Random prefetch

  • Buffer pool partitioning

  • Multiple buffer pools

1. Técnicas de Otimização

• Locality of Reference

  • Temporal locality

  • Spatial locality

  • Sequential access

  • Random access

2. Monitoramento e Tuning

• Métricas Chave

  • Hit ratio

  • Miss ratio

  • Response time

  • Throughput

• Ferramentas

  • Performance counters

  • Memory profilers

  • I/O statistics

  • Cache analytics

1. Design Considerations

• Workload Analysis

  • Read/write patterns

  • Access frequency

  • Data volume

  • Concurrency requirements